package leetcode_day._2021._202112._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/5 17:23
 * 超级次方
 * 你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
 * 算法：数学
 * a 的 b 次方 = a 的 (⌊b / 10⌋ * 10 + b % 10) 次方 = a 的 ⌊b / 10⌋ * 10 方 * a 的 b % 10 次方
 */
public class _05_372 {
    static int MOD = 1337;
    public static void main(String[] args) {
        System.out.println(new _05_372().superPow(2, new int[]{3}));
    }

    public int superPow(int a, int[] b) {
        return dfs(a, b, b.length - 1);
    }
    int dfs(int a, int[] b, int u) {
        if (u == -1) return 1;
        return quick(dfs(a, b, u - 1), 10) * quick(a, b[u]) % MOD;
    }
    int quick(int a, int b) {
        int res = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

}
